#include <iostream>
using namespace std;

struct TNode
{
	int data;
	TNode* left;
	TNode* right;
	TNode(int val):data(val),left(NULL),right(NULL){};
};
void Add(TNode* t,int val){
	if(t == NULL){
		t = new TNode(val);
	}
	else{
		if(t->data > val){
			if(t->left == NULL){
				TNode* tmp = new TNode(val);
				t->left = tmp;
			}
			else{
				Add(t->left,val);
			}
		}
		else{
			if(t->right == NULL){
				TNode* tmp = new TNode(val);
				t->right = tmp;
			}
			else{
				Add(t->right,val);
			}
		}
	}
}
void Print(TNode* root){
	if(root){
		Print(root->left);
		cout<<root->data<<"  ";
		Print(root->right);
	}
}
int Depth(TNode* root){
	if(root == NULL){
		return 0;
	}
	int left_depth = Depth(root->left);
	int right_depth = Depth(root->right);
	return left_depth>right_depth?(left_depth+1):(right_depth+1);
}
void PrintLevel(TNode* tnode,int level){
	if(tnode == NULL){
		return ;
	}
	else{
		if(level == 0){
			cout<<tnode->data<<"  ";
		}
		else{
			PrintLevel(tnode->left,level-1);
			PrintLevel(tnode->right,level-1);
		}
	}
}
void PrintLevelOrder(TNode* tnode,int level){
	int depth = Depth(tnode);
	for(int i = 0;i < depth;i++){
		PrintLevel(tnode,i);
		cout<<endl<<"----------------------"<<endl;
	}
}
int main(int argc, char const *argv[])
{
	int arr[10] = {5,7,1,2,3,9,8,0,4,6};
	TNode* root = NULL;
	for(int i = 0;i < 10;i++){
		if(i == 0){
			root = new TNode(arr[i]);
		}
		else{
			Add(root,arr[i]);
		}
	}
	Print(root);
	cout<<endl;
	cout<<Depth(root)<<endl;
	cout<<endl;
	PrintLevelOrder(root,Depth(root));
	return 0;
}